The present invention relates to a method of controlling the congestion of information on a network.
Networks comprised of high performance switching elements are important for the high-speed transport of information, which may include text, voice, and video information. Emerging networks, such as broadband integrated services digital networks (B-ISDN) are designed to support a variety of applications such as interactive and distributed audio, video and data communications. The principle transfer mode for B-ISDN is called asynchronous transfer mode (ATM). ATM is a high-bandwidth, low delay packet switching and multiplexing technique.
In the switching elements used by these types of networks, cells or packets of information are received by a plurality of input ports which transport the packets to predefined output ports. Many times, one or more of the switching elements receives packets faster that it can dispose of them. As a result, the packets build up in a local buffer memory associated with the switching element, causing an overflow situation. Methods used to manage buffer memory by either preventing an overflow situation or determining which packets of information will be lost include interstage buffer management schemes and intrastage buffer management schemes. Interstage buffer management schemes regulate the movement of packets between stages of switching elements by using available buffer memory upstream of the congested switching element to store packets intended for the congested element. Intrastage buffer management schemes regulate the movement of packets within a given stage by managing the competition between output queues within the stage.
An example of an interstage buffer management scheme is a backpressure control scheme. Backpressure control occurs when a switching element Y considers its local buffer memory to be too full. Switching element Y sends a backpressure signal to switching element X which is located immediately upstream of switching element Y. Information destined for switching element Y is stored in the buffer memory of switching element X. When the local buffer memory of switching element X becomes too full, it sends a backpressure signal to the switching element located immediately upstream and the process repeats itself. The process can be carried back all the way to the first switching element in the transmission path.
By using the backpressure control in this manner, all of the switching elements upstream of Y can become monopolized by the information destined for congested switching element Y, thereby hindering the overall throughput of information. As such, backpressure control schemes are limited because they only regulate in an upstream direction. The backpressure scheme causes the congestion originating from the downstream element to be propagated upstream, thereby preventing packets from being transmitted to other downstream elements which are not congested.
In networks comprised of switching elements having shared local buffer memory, overload situations may be overcome by using local or intrastage buffer management schemes. The local buffer management schemes include pushout, allocation and limit-based schemes. The local buffer management schemes manage competition between output queues within a given switching element.
The pushout scheme is used when switching element Y has a full local buffer memory. Switching element Y continues to receive any packets arriving from upstream switching element X. Space is made for the new packets in switching element Y's local buffer memory by pushing out a packet from the longest output queue in switching element Y. The new packet usurps the physical memory location of the pushed out packet, but the new packet can then be assigned to a different logical output queue. The pushout scheme allows a packet destined to a less congested output queue to reach its destination at the expense of packets in longer queues.
In the allocation scheme, each switching element allocates a small amount of its local buffer memory to each of its output queues. The remainder of the memory is shared among all of the output queues. A packet arriving from an upstream switching element is dropped only if the memory allocated to its output queue is full and the shared memory is also full.
The limit-based scheme is used to set a limit on the length of each individual output queue in the local buffer memory of a given switching element. A packet arriving from an upstream switching element is dropped if it is destined for an output queue which has reached its length limit. Arriving packets are also dropped if the local buffer memory is completely full, regardless of whether the destined output queue has reached its limit.
The local buffer management schemes are able to discriminate between the different output queues within the element so that congested output queues which are dominating the shared memory lose packets prior to output queues which are receiving a fewer number of packets. However, each of the local buffer management schemes described above is limited to regulating packet flow within the element and therefore is limited by the amount of memory available to the element.